package Algorithm.greedyAlgorithm;

/**
 * 55. 跳跃游戏 https://leetcode.cn/problems/jump-game/description/
 */
public class CanJump {

    /**
     * 思路：从0遍历到能跳到的最远下标k，遍历过程中计算下标所能跳到的最远下标来更新k，若k>=nums.length-1，则能跳到最后一个下标
     */
    public boolean canJump(int[] nums) {
        //记录当前能跳到的最远下标，初始为0
        int k = 0;
        for(int i = 0;i <= k;i++) {
            //更新能跳到的最远下标
            k = Math.max(k, i+nums[i]);
            //若能跳到的最远下标已包括最后一个下标，则返回true
            if(k >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }






    //递归法 超时
    public boolean canJump2(int[] nums) {
        return canJump(nums, nums.length);
    }

    public boolean canJump(int[] nums, int length) {
        if(length == 1) return true;
        for(int i = length - 2;i >= 0;i--) {
            if(nums[i] >= length - 1 - i) {
                if(canJump(nums, i+1)) return true;
            }
        }
        return false;
    }
}
